home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / hash / RCS / Hash_CreateEntry.c,v < prev    next >
Text File  |  1989-11-30  |  6KB  |  267 lines
  1. head     1.3;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.3
  10. date     88.07.28.17.57.23;  author ouster;  state Exp;
  11. branches ;
  12. next     1.2;
  13.  
  14. 1.2
  15. date     88.07.25.10.53.29;  author ouster;  state Exp;
  16. branches ;
  17. next     1.1;
  18.  
  19. 1.1
  20. date     88.06.20.09.30.19;  author ouster;  state Exp;
  21. branches ;
  22. next     ;
  23.  
  24.  
  25. desc
  26. @@
  27.  
  28.  
  29. 1.3
  30. log
  31. @Lint.
  32. @
  33. text
  34. @/* 
  35.  * Hash_CreateEntry.c --
  36.  *
  37.  *    Source code for the Hash_CreateEntry library procedure.
  38.  *
  39.  * Copyright 1988 Regents of the University of California
  40.  * Permission to use, copy, modify, and distribute this
  41.  * software and its documentation for any purpose and without
  42.  * fee is hereby granted, provided that the above copyright
  43.  * notice appear in all copies.  The University of California
  44.  * makes no representations about the suitability of this
  45.  * software for any purpose.  It is provided "as is" without
  46.  * express or implied warranty.
  47.  */
  48.  
  49. #ifndef lint
  50. static char rcsid[] = "$Header: Hash_CreateEntry.c,v 1.2 88/07/25 10:53:29 ouster Exp $ SPRITE (Berkeley)";
  51. #endif not lint
  52.  
  53. #include <hash.h>
  54. #include <list.h>
  55. #include <stdlib.h>
  56. #include <string.h>
  57.  
  58. /*
  59.  * Utility procedures defined in other files:
  60.  */
  61.  
  62. extern Hash_Entry *    HashChainSearch();
  63. extern int        Hash();
  64.  
  65. /* 
  66.  * The following defines the ratio of # entries to # buckets
  67.  * at which we rebuild the table to make it larger.
  68.  */
  69.  
  70. static rebuildLimit = 3;
  71.  
  72. /*
  73.  *---------------------------------------------------------
  74.  *
  75.  * RebuildTable --
  76.  *    This local routine makes a new hash table that
  77.  *    is larger than the old one.
  78.  *
  79.  * Results:    
  80.  *     None.
  81.  *
  82.  * Side Effects:
  83.  *    The entire hash table is moved, so any bucket numbers
  84.  *    from the old table are invalid.
  85.  *
  86.  *---------------------------------------------------------
  87.  */
  88.  
  89. static void
  90. RebuildTable(tablePtr)
  91.     Hash_Table     *tablePtr;        /* Table to be enlarged. */
  92. {
  93.     int          oldSize;
  94.     int          bucket;
  95.     List_Links         *oldBucketPtr;
  96.     register Hash_Entry  *hashEntryPtr;
  97.     register List_Links     *oldHashList;
  98.  
  99.     oldBucketPtr = tablePtr->bucketPtr;
  100.     oldSize = tablePtr->size;
  101.  
  102.     /* 
  103.      * Build a new table 4 times as large as the old one. 
  104.      */
  105.  
  106.     Hash_InitTable(tablePtr, tablePtr->size * 4, tablePtr->keyType);
  107.  
  108.     for (oldHashList = oldBucketPtr; oldSize > 0; oldSize--, oldHashList++) {
  109.     while (!List_IsEmpty(oldHashList)) {
  110.         hashEntryPtr = (Hash_Entry *) List_First(oldHashList);
  111.         List_Remove((List_Links *) hashEntryPtr);
  112.         switch (tablePtr->keyType) {
  113.         case HASH_STRING_KEYS:
  114.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.name);
  115.             break;
  116.         case HASH_ONE_WORD_KEYS:
  117.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.ptr);
  118.             break;
  119.         default:
  120.             bucket = Hash(tablePtr, (Address) hashEntryPtr->key.words);
  121.             break;
  122.         }
  123.         List_Insert((List_Links *) hashEntryPtr, 
  124.         LIST_ATFRONT(&(tablePtr->bucketPtr[bucket])));
  125.         tablePtr->numEntries++;
  126.     }
  127.     }
  128.  
  129.     free((Address) oldBucketPtr);
  130. }
  131.  
  132. /*
  133.  *---------------------------------------------------------
  134.  *
  135.  * Hash_CreateEntry --
  136.  *
  137.  *    Searches a hash table for an entry corresponding to
  138.  *    key.  If no entry is found, then one is created.
  139.  *
  140.  * Results:
  141.  *    The return value is a pointer to the entry.  If *newPtr
  142.  *    isn't NULL, then *newPtr is filled in with TRUE if a
  143.  *    new entry was created, and FALSE if an entry already existed
  144.  *    with the given key.
  145.  *
  146.  * Side Effects:
  147.  *    Memory may be allocated, and the hash buckets may be modified.
  148.  *---------------------------------------------------------
  149.  */
  150.  
  151. Hash_Entry *
  152. Hash_CreateEntry(tablePtr, key, newPtr)
  153.     register Hash_Table *tablePtr;    /* Hash table to search. */
  154.     Address key;            /* A hash key. */
  155.     Boolean *newPtr;            /* Filled in with TRUE if new entry
  156.                          * created, FALSE otherwise. */
  157. {
  158.     register Hash_Entry *hashEntryPtr;
  159.     register int     *hashKeyPtr;
  160.     register int     *keyPtr;
  161.     List_Links         *hashList;
  162.  
  163.     keyPtr = (int *) key;
  164.  
  165.     hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
  166.     hashEntryPtr = HashChainSearch(tablePtr, (Address) keyPtr, hashList);
  167.  
  168.     if (hashEntryPtr != (Hash_Entry *) NULL) {
  169.     if (newPtr != NULL) {
  170.         *newPtr = FALSE;
  171.     }
  172.         return hashEntryPtr;
  173.     }
  174.  
  175.     /* 
  176.      * The desired entry isn't there.  Before allocating a new entry,
  177.      * see if we're overloading the buckets.  If so, then make a
  178.      * bigger table.
  179.      */
  180.  
  181.     if (tablePtr->numEntries >= rebuildLimit * tablePtr->size) {
  182.     RebuildTable(tablePtr);
  183.     hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
  184.     }
  185.     tablePtr->numEntries += 1;
  186.  
  187.     /*
  188.      * Not there, we have to allocate.  If the string is longer
  189.      * than 3 bytes, then we have to allocate extra space in the
  190.      * entry.
  191.      */
  192.  
  193.     switch (tablePtr->keyType) {
  194.     case HASH_STRING_KEYS:
  195.         hashEntryPtr = (Hash_Entry *) malloc((unsigned)
  196.             (sizeof(Hash_Entry) + strlen((char *) keyPtr) - 3));
  197.         strcpy(hashEntryPtr->key.name, (char *) keyPtr);
  198.         break;
  199.     case HASH_ONE_WORD_KEYS:
  200.         hashEntryPtr = (Hash_Entry *) malloc(sizeof(Hash_Entry));
  201.         hashEntryPtr->key.ptr = (Address) keyPtr;
  202.         break;
  203.     case 2:
  204.         hashEntryPtr = 
  205.         (Hash_Entry *) malloc(sizeof(Hash_Entry) + sizeof(int));
  206.         hashKeyPtr = hashEntryPtr->key.words;
  207.         *hashKeyPtr++ = *keyPtr++;
  208.         *hashKeyPtr = *keyPtr;
  209.         break;
  210.     default: {
  211.         register     n;
  212.  
  213.         n = tablePtr->keyType;
  214.         hashEntryPtr = (Hash_Entry *) 
  215.             malloc((unsigned) (sizeof(Hash_Entry)
  216.             + (n - 1) * sizeof(int)));
  217.         hashKeyPtr = hashEntryPtr->key.words;
  218.         do { 
  219.         *hashKeyPtr++ = *keyPtr++; 
  220.         } while (--n);
  221.         break;
  222.     }
  223.     }
  224.  
  225.     hashEntryPtr->clientData = (ClientData) NULL;
  226.     List_Insert((List_Links *) hashEntryPtr, LIST_ATFRONT(hashList));
  227.  
  228.     if (newPtr != NULL) {
  229.     *newPtr = TRUE;
  230.     }
  231.     return hashEntryPtr;
  232. }
  233. @
  234.  
  235.  
  236. 1.2
  237. log
  238. @Lint.
  239. @
  240. text
  241. @d17 1
  242. a17 1
  243. static char rcsid[] = "$Header: Hash_CreateEntry.c,v 1.1 88/06/20 09:30:19 ouster Exp $ SPRITE (Berkeley)";
  244. d162 2
  245. a163 2
  246.         hashEntryPtr = (Hash_Entry *) malloc(sizeof(Hash_Entry) + 
  247.             strlen((char *) keyPtr) - 3);
  248. d182 2
  249. a183 1
  250.             malloc(sizeof(Hash_Entry) + (n - 1) * sizeof(int));
  251. @
  252.  
  253.  
  254. 1.1
  255. log
  256. @Initial revision
  257. @
  258. text
  259. @d17 1
  260. a17 1
  261. static char rcsid[] = "$Header: proto.c,v 1.2 88/03/11 08:39:08 ouster Exp $ SPRITE (Berkeley)";
  262. d20 4
  263. a23 2
  264. #include "hash.h"
  265. #include "list.h"
  266. @
  267.